package com.yiwenup.leetcode.offer;

import java.util.LinkedHashMap;

/**
 * https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
 **/
public class No050 {
    /**
     * 执行用时：31 ms, 在所有 Java 提交中击败了43.52%的用户
     * 内存消耗：38.5 MB, 在所有 Java 提交中击败了81.98%的用户
     */
    public char firstUniqChar(String s) {
        LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        for (Character c : map.keySet()) {
            if (map.get(c) == 1) {
                return c;
            }
        }
        return ' ';
    }

    /**
     * 执行用时：24 ms, 在所有 Java 提交中击败了71.24%的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了43.11%的用户
     */
    public char firstUniqChar2(String s) {
        LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (Character c : map.keySet()) {
            if (map.get(c) == 1) {
                return c;
            }
        }
        return ' ';
    }

    /**
     * 执行用时：4 ms, 在所有 Java 提交中击败了98.43%的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了14.42%的用户
     */
    public char firstUniqChar3(String s) {
        int[] ints = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            ints[c - 'a']++;
        }
        for (char c : chars) {
            if (ints[c - 'a'] == 1) {
                return c;
            }
        }
        return ' ';
    }

    /**
     * 执行用时：5 ms, 在所有 Java 提交中击败了94.60%的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了37.83%的用户
     */
    public char firstUniqChar4(String s) {
        int[] ints = new int[26];
        for (int i = 0; i < s.length(); i++) {
            ints[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (ints[s.charAt(i) - 'a'] == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }

}
